math test - CF #456(div 2) D-Fishes

发表于

这是个数学题a…
所有的\(r*r\)的scoop的数目为\((n-r+1)*(m-r+1)\)
其中包含坐标\((x,y)\)的scoop的数目为（坐标index从1开始）\[f(x,y)=(min(n+1,x+r)-max(x,r))*(min(m+1,y+r)-max(y,r))\]

\(f(x_0,y)\)在固定x坐标的情况下，\(f(x_0,y)\)先增后减，最大值点为\(\left \lfloor \frac{m+1}{2} \right \rfloor\)

全局最大值点为\((\left \lfloor \frac{n+1}{2} \right \rfloor,\left \lfloor \frac{m+1}{2} \right \rfloor)\)

因此，可以得到的算法为：1.从每一行的最大值点开始，向两边扩展；2.从全局最大值点开始BFS

题目说精确度1e-9，小数要输出到第9位以后，默认double输出6位导致WA
代码实现算法1，其中’D’表示decrease，向左边扩展，‘I’表示increase，向右边扩展

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m, r, k;

struct Point {
  int x, y;
  ll val;
  char type;
  Point(int x, int y, char type)
  : x(x), y(y), type(type) {
    val = (min(n + 1, x + r) - max(x, r)) * 1LL * (min(m + 1, y + r) - max(y, r));
  }
  bool operator<(const Point& p) const {
    return val < p.val;
  }
};

void solve() {
  priority_queue<Point, vector<Point> > que;
  for (int x = 1; x <= n; x++) {
    int mid = (m + 1) / 2;
    que.push(Point(x, mid, 'D'));
    if (mid + 1 <= m) {
      que.push(Point(x, mid + 1, 'I'));
    }
  }
  ll sum = 0;
  while (k--) {
    Point p = que.top(); que.pop();
    sum += p.val;
    if (p.type == 'D' && p.y - 1 >= 1) {
      que.push(Point(p.x, p.y - 1, 'D'));
    }
    if (p.type == 'I' && p.y + 1 <= m) {
      que.push(Point(p.x, p.y + 1, 'I'));
    }
  }
  printf("%.9lf\n", (double)sum / (n - r + 1) / (m - r + 1));
}

int main() {
  scanf("%d %d %d %d", &n, &m, &r, &k);
  solve();
  return 0;
}